Digital data is transmitted from one user to another user via a switched network usually in the form of data packets. In one standard method of transmitting digital data, the data packets are switched through the network via virtual channels. The virtual channels are prepared as a result of a server routing the packets through the switched network via a path that has been determined by the server to satisfy the data traffic requirements for the particular data being transmitted. This type of a system is referred to as an asynchronous transfer mode network (ATM).
In ATM networks, data is packeted by the user application into blocks of data referred to as "cells." Each cell is a portion of data to be transmitted from one user application to another user application via the ATM switched network. The ATM network, through a series of ATM switches, provides a connection through which a user application may communicate cells to another user application. Each connection is characterized by a peak cell rate, which refers to the maximum number of cells that can be transmitted across a given connection per unit time. The ATM connections can also be characterized by a "sustainable cell rate," which refers to the cell rate that can be sustained over longer transmission durations, rather than the shorter, burstier transmissions that characterize the "peak cell rate." Those of ordinary skill in the art will understand the "peak cell rate" and the "sustainable cell rate," as these phrases are used to characterize ATM connections.
Although ATM networks can take a variety of different forms, they are generally characterized by interconnected routers and other associated hardware to switch data packets provided to the network from one point in the network to another point in the network. Within each ATM switch in the ATM network, data packets are provided via an ingress port, through the switch, and to an egress port. The data packets provided to each ingress port may have associated headers which indicate the routing, i.e., the virtual channel connections, through which the data is to travel within the ATM switched network. In this way, the data cells provided to an ingress port are switched through the associated ATM switch to an egress port, and ultimately from switch to switch through the ATM network.
Those of ordinary skill in the art will understand that packets traveling through an ATM switch must be prioritized for distribution. That is, an ATM network has, for each possible connection within it, limited sustainable cell rates for the transmission of packets. If a multiple number of user applications are providing packets to the ATM switched network for transmission over a particular connection, the cells being provided to it must determine which cells will travel first down a particular connection. Such prioritization of incoming data cells is referred to as "queuing."
A number of different methods have been provided for queuing cells through an ATM switched network, including queuing them based on a first-in prioritization scheme. Unfortunately, these schemes do not take into account the relative importance of the different cells within different transmission slots.